# @Time    :2025/4/14 11:50
from collections import deque


class Node:
    def __init__(self, data):
        self.data = data
        self.right = None
        self.left = None


class Tree:
    def __init__(self):
        self.__root = None
        self.__size = 0

    @property
    def size(self):
        return self.__size

    def is_empty(self):
        return self.__size == 0

    def search(self, item):
        """" 查找节点是否存在 """
        return self.search_pos(item)[0] is not None

    def print_tree(self):
        """打印树的结构"""

        # 先得到树的层数
        def get_layer(node):
            """递归计算树的层数"""
            if node is None:
                return 0
            else:
                left_depth = get_layer(node.left)
                right_depth = get_layer(node.right)
                return max(left_depth, right_depth) + 1

        layer = get_layer(self.__root)

        # 层序遍历并打印
        queue = deque([(self.__root, 1)])
        current_level = 1
        while queue:
            node, level = queue.popleft()
            if level > current_level:
                print()
                current_level += 1
            if node:
                print(f"{node.data:^{20 * layer // 2 ** (level - 1)}}", end="")
            else:
                print(f"{"N":^{20 * layer // 2 ** (level - 1)}}", end="")
            if level < layer:
                if node:
                    queue.append((node.left, level + 1))
                    queue.append((node.right, level + 1))
                else:
                    queue.append((None, level + 1))
                    queue.append((None, level + 1))
        print()

    def search_pos(self, item):
        parent = None
        current = self.__root  # 当前节点指向根
        # 如果当前节点存在 进入循环
        while current:
            if item == current.data:  # 如果你查找的元素是当前节点的值,就不再查找，将当前节点 就是父节点
                break
            parent = current
            current = current.left if item < current.data else current.right
        return current, parent

    def add(self, item):
        """向二叉搜索树中插入节点"""
        # 封装个节点
        node = Node(item)
        # 1,先看树是否空，空 就将封装的节点指向根节点root
        if self.is_empty():
            self.__root = node
        else:
            # 2,若不为空，就查找当前节点和父节点
            current, parent = self.search_pos(item)
            # 3,如果查找的节点已存在 就不用插入了就返回
            if current:
                return
            # 4,如果节点之前不存在，则插入父节点的左节点或者右节点
            # 二叉树 左小右大的原则。如果插入的数据小于父节点，就将封装的节点给左节点，反之 给右节点
            if parent.data > item:
                parent.left = node
            else:
                parent.right = node
        self.__size += 1

    def remove(self, item):
        """从二叉搜索树中删除节点"""
        current, parent = self.search_pos(item)
        if not current:  # 如果要删除的节点不存在就返回
            return

            # 1，如果要删除的是叶子节点（没有子节点）
        # 没有左节点并且没有右节点
        if not current.left and not current.right:
            # 如果存在父节点，
            if parent:
                # 如果当前节点是父的左子节点，就将左子节点置为None,反之，右置为None
                if parent.left == current:
                    parent.left = None
                else:
                    parent.right = None
            # 没有父节点，那就是仅自己一个 节点（那就是根节点）
            else:
                self.__root = None

        # 2，如果要删除的节点有一个子节点
        # 没有左节点或者没有右节点
        elif not current.left or not current.right:
            # 获取当前要删除的节点的子节点
            child = current.left if current.left else current.right
            # 判断删除的节点是不是根
            if parent:
                # 说明删除的不是根
                if parent.left == current:
                    parent.left = child
                else:
                    parent.right = child
                # 没有父节点，那就是仅自己一个 节点（那就是根节点）
            else:
                self.__root = child


        # 3，如果要删除的节点有两个子节点
        else:
            # 如果删除的节点有两个子节点
            successor = self.__get_min(current.right)  # 找到右子树中最小节点
            successor_data = successor.data  # 获取后继节点的值
            self.remove(successor_data)  # 把后继节点值删掉
            current.data = successor_data  # 用后继节点的值上移替代当前节点的值

        self.__size -= 1

    def __get_min(self, node):
        """找到当前子树的最小节点"""
        # 左小右大 ，通过不断访问左子节点 找到最小节点
        current = node
        while current.left:
            current = current.left
        return current

    def for_each(self, func, order="inorder"):
        """遍历树，默认中序遍历"""
        match order:
            case "inorder":
                self.__inorder_traversal(func)
            case "preorder":
                self.__preorder_traversal(func)
            case "postorder":
                self.__postorder_traversal(func)
            case "levelorder":
                self.__levelorder_traversal(func)

    def __inorder_traversal(self, func):
        """深度优先搜索：中序遍历"""

        def inorder(node):
            if node:
                inorder(node.left)
                func(node.data)
                inorder(node.right)

        inorder(self.__root)

    def __preorder_traversal(self, func):
        """深度优先搜索：前序遍历"""

        def preorder(node):
            if node:
                func(node.data)
                preorder(node.left)
                preorder(node.right)

        preorder(self.__root)

    def __postorder_traversal(self, func):
        """深度优先搜索：后序遍历"""

        def postorder(node):
            if node:
                postorder(node.left)
                postorder(node.right)
                func(node.data)

        postorder(self.__root)

    def __levelorder_traversal(self, func):
        """广度优先搜索：层序遍历"""
        queue = deque()
        queue.append(self.__root)
        while queue:
            node = queue.popleft()
            func(node.data)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)


t = Tree()

t.add(3)
t.add(12)
t.add(1)
t.print_tree()
print("--" * 30)
t.for_each(print, order="inorder")
